#include <bits/stdc++.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>

using namespace std;

//string testFile = "data/1004812/test_data.txt";
//string testFile = "data/2861665_639096/test_data.txt";
//string testFile = "data/3512444_697518/test_data.txt";
string testFile = "data/19630345/test_data.txt";
//string testFile = "data/std/test_data.txt";

string resultFile = "rslt.txt";

typedef struct Node{
	int id;
	uint money;
	bool operator<(const Node &other)const{
		return id<other.id;
	}
	bool operator==(const Node &other)const{
		return id==other.id;
	}
}Node;

int account_num = 0;
uint inputs[2*2000000];
uint accts[2*2000000];
vector<Node> G[2000000];
vector<Node> RG[2000000];

char account_chars[2000000][12];
short length[2000000];
char buf[77*20000000];

pthread_mutex_t g_mutex = PTHREAD_MUTEX_INITIALIZER;

/*线程1变量*/
int head_1;
int canReach_1[2000000][2];
vector<Node> ptp_1[2000000];
vector<vector<int>> ans3_1;
vector<vector<int>> ans4_1;
vector<vector<int>> ans5_1;
vector<vector<int>> ans6_1;
vector<vector<int>> ans7_1;
bool vis_1[2000000];
int path_1[7], pay_1[7];
int r1;
/**********************/
int head_2;

uint parse_1(char** s){
	char *p = *s;
	uint val = *(p++) - '0';
	while(*p != ',') val = 10*val + *(p++) - '0';
	*s = p+1;
	return val;
}
uint parse_2(char** s){
	char *p = *s;
	uint val = *(p++) - '0';
	while(*p != '\r' && *p != '\n') val = 10*val + *(p++) - '0';
	*s = *p=='\r' ? p+2:p+1;
	return val;
}
void parse_to_char(uint a, char *dest, int &k){
	int n=0;
	do{dest[n++] = a%10+'0';}while((a/=10)>0);
	reverse(dest, dest+n);
	dest[n++]=',';
	length[k]=n;
}
void loadData_and_createGrap(){
	int fd = open(testFile.c_str(), O_RDONLY);
    int size = lseek(fd, 0, SEEK_END);
    char* p_map =(char*)mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
    close(fd);
	char *p = p_map;
	int n=0;//n表示文件中的记录数
	uint money[2000000];
	while(*p != '\0'){
		inputs[n]=parse_1(&p);
		inputs[n+2000000]=parse_1(&p);
		money[n++]=parse_2(&p);
	}
	memcpy(accts, inputs, 4*n);
	memcpy(accts+n, inputs+2000000, 4*n);  
	sort(accts, accts+2*n);//排序
	account_num = unique(accts, accts+2*n) - accts;//去重
	unordered_map<uint, int> idHash;
	for(int i=0; i<account_num; i++) idHash[accts[i]]=i;
	Node node;
	for(int i=0,a=0,b=0, m=0; i<n; ++i,++m){
		a=idHash[inputs[i+0]];
		b=idHash[inputs[i+2000000]];
		if(a==b) continue;
		G[a].push_back(Node{b,money[m]});
		RG[b].push_back(Node{a,money[m]});
	}
	for(int i=0; i<account_num; i++) {sort(G[i].begin(),G[i].end());sort(RG[i].begin(),RG[i].end());parse_to_char(accts[i], account_chars[i], i);}
	munmap(p_map, size);
}

inline bool check(const uint &x, const uint &y){
	return x<=5ll*y && y<=3ll*x;
}

/*线程1*/
void adpth3_1(){
	uint py1=pay_1[0],py2,py3;
	int pos = canReach_1[path_1[1]][1];
	for(Node &node:ptp_1[pos]){
		if(!check(py1,node.money)) continue;
		py3 = (*find(G[node.id].begin(),G[node.id].end(), Node{path_1[0],0})).money;
		if(!check(node.money,py3) || !check(py3,py1)) continue;
		ans3_1.push_back({path_1[0],path_1[1],node.id});
	}
}
void adpth4_1(){
	uint py1=pay_1[0],py2=pay_1[1],py3,py4;
	int pos = canReach_1[path_1[2]][1];
	for(Node &node:ptp_1[pos]){
		if(vis_1[node.id]) continue;
		if(!check(py2,node.money)) continue;
		py4 = (*find(G[node.id].begin(),G[node.id].end(), Node{path_1[0],0})).money;
		if(!check(node.money,py4) || !check(py4,py1)) continue;
		ans4_1.push_back({path_1[0],path_1[1],path_1[2],node.id});
	}
}
void adpth5_1(){
	uint py1=pay_1[0],py2=pay_1[1],py3=pay_1[2],py4,py5;
	int pos = canReach_1[path_1[3]][1];
	for(Node &node:ptp_1[pos]){
		if(vis_1[node.id]) continue;
		if(!check(py3,node.money)) continue;
		py5 = (*find(G[node.id].begin(),G[node.id].end(), Node{path_1[0],0})).money;
		if(!check(node.money,py5) || !check(py5,py1)) continue;
		ans5_1.push_back({path_1[0],path_1[1],path_1[2],path_1[3],node.id});
	}
}
void adpth6_1(){
	uint py1=pay_1[0],py2=pay_1[1],py3=pay_1[2],py4=pay_1[3],py5,py6;
	int pos = canReach_1[path_1[4]][1];
	for(Node &node:ptp_1[pos]){
		if(vis_1[node.id]) continue;
		if(!check(py4,node.money)) continue;
		py6 = (*find(G[node.id].begin(),G[node.id].end(), Node{path_1[0],0})).money;
		if(!check(node.money,py6) || !check(py6,py1)) continue;
		ans6_1.push_back({path_1[0],path_1[1],path_1[2],path_1[3],path_1[4],node.id});
	}
}
void adpth7_1(){
	uint py1=pay_1[0],py2=pay_1[1],py3=pay_1[2],py4=pay_1[3],py5=pay_1[4],py6,py7;
	int pos = canReach_1[path_1[5]][1];
	for(Node &node:ptp_1[pos]){
		if(vis_1[node.id]) continue;
		if(!check(py5,node.money)) continue;
		py7 = (*find(G[node.id].begin(),G[node.id].end(), Node{path_1[0],0})).money;
		if(!check(node.money,py7) || !check(py7,py1)) continue;
		ans7_1.push_back({path_1[0],path_1[1],path_1[2],path_1[3],path_1[4],path_1[5],node.id});
	}
}
void dep5_1(int &u){
	vis_1[u] = true;
	for(Node &node:G[u]){
		if(node.id<=path_1[0] || vis_1[node.id]) continue;
		if(!check(pay_1[3],node.money)) continue;
		path_1[5]=node.id;
		pay_1[4]=node.money;
		if(canReach_1[node.id][0]==path_1[0]) adpth7_1();
	}
	vis_1[u] = 0;
}
void dep4_1(int &u){
	vis_1[u] = true;
	for(Node &node:G[u]){
		if(node.id<=path_1[0] || vis_1[node.id]) continue;
		if(!check(pay_1[2],node.money)) continue;
		path_1[4]=node.id;
		pay_1[3]=node.money;
		if(canReach_1[node.id][0]==path_1[0]) adpth6_1();
		dep5_1(node.id);
	}
	vis_1[u] = 0;
}
void dep3_1(int &u){
	vis_1[u] = 1;
	for(Node &node:G[u]){
		if(node.id<=path_1[0] || vis_1[node.id]) continue;
		if(!check(pay_1[1],node.money)) continue;
		path_1[3]=node.id;
		pay_1[2] = node.money;
		if(canReach_1[node.id][0]==path_1[0]) adpth5_1();
		dep4_1(node.id);
	}
	vis_1[u] = 0;
}
void dep2_1(int &u){
	vis_1[u] = 1;
	for(Node &node:G[u]){
		if(node.id<=path_1[0] || vis_1[node.id]) continue;
		if(!check(pay_1[0],node.money)) continue;
		path_1[2] = node.id;
		pay_1[1] = node.money;
		if(canReach_1[node.id][0]==path_1[0]) adpth4_1();
		dep3_1(node.id);
	}
	vis_1[u] = 0;
}
void dep1_1(int &u){
	vis_1[u] = 1;
	for(Node &node:G[u]){
		if(node.id<=u) continue;
		path_1[1] = node.id;
		pay_1[0] = node.money;
		if(canReach_1[node.id][0]==u) adpth3_1();
		dep2_1(node.id);
	}
	vis_1[u] = 0;
}
void solve_1(){
	auto start = chrono::steady_clock::now();
	bool flag = false;
	memset(vis_1, 0, sizeof(vis_1));
	for(int i=0; i<account_num; i++){canReach_1[i][0]=-1;}
	Node tmp;
	int headPos,layerPos;
	while(1){
		pthread_mutex_lock(&g_mutex);
		if((head_2 - head_1) <= 1) flag=true;
        head_1++;
        pthread_mutex_unlock(&g_mutex);
        if(flag) break;
		if(G[head_1].size()<1 || RG[head_1].size()<1) continue;
		headPos = 0;
		for(Node &node1:RG[head_1]){//head<--n1
			int &n1 = node1.id;
			if(n1<head_1) continue;
			for(Node &node2:RG[n1]){//head<--n1--<n2
				int &n2 = node2.id;
				if(n2 <= head_1) continue;
				if(canReach_1[n2][0] != head_1){
					canReach_1[n2][0] = head_1;
					canReach_1[n2][1] = headPos;
					ptp_1[headPos++].clear();
				}
				ptp_1[canReach_1[n2][1]].push_back(Node{node1.id,node2.money});
			}
		}
		path_1[0] = head_1;
		dep1_1(head_1);
	}
	auto end = chrono::steady_clock::now();
	double cost_t = chrono::duration<double,std::milli>(end-start).count()/1000;
	cout << "solve_1 -const- : " << cost_t  << "s" <<"       head_1 = "<<head_1<<endl;
}

int main(int argc, char* argv[]){
	clock_t startTime = clock();
	loadData_and_createGrap();
	clock_t endTime = clock();
	cout << "LoadDataAndCreate: " << (float)(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
	
	
	head_1 = -1;
	head_2 =account_num;
	auto start = chrono::steady_clock::now();
	vector<thread> threadpool(2);
	threadpool[0] = thread(&solve_1);
	//threadpool[1] = thread(&solve_2);
	threadpool[0].join();
	//threadpool[1].join();
	auto end = chrono::steady_clock::now();
	double cost_t = chrono::duration<double,std::milli>(end-start).count()/1000;
	cout << "compute : " << cost_t  << "s" << endl;
	
	
	
	startTime = clock();
	//save();
	endTime = clock();
	cout << "save: " << (float)(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
	
	
	cout<<endl;
	cout<<"p3_1 = "<<ans3_1.size()<<endl;
	cout<<"p4_1 = "<<ans4_1.size()<<endl;
	cout<<"p5_1 = "<<ans5_1.size()<<endl;
	cout<<"p6_1 = "<<ans6_1.size()<<endl;
	cout<<"p7_1 = "<<ans7_1.size()<<endl<<endl;
	int all = ans3_1.size()+ans4_1.size()+ans5_1.size()+ans6_1.size()+ans7_1.size();
	cout<<"all_loops = "<<all<<endl;
	exit(0);
}